package ch09_;

import java.util.Arrays;

public class Ch9_5 {
	public static void permute(String s) {
		permute(s, 0);
	}

	private static void permute(String s, int position) {
		if (position == s.length() - 1) {
			System.out.println(s);
		} else {
			char[] ca = s.toCharArray();
			for (int i = position; i < s.length(); i++) {
				swap(ca, position, i);
				permute(new String(ca), position + 1);
				swap(ca, i, position);
			}
		}
	}

	public static void dupPermute(String s) {
		char[] ca = s.toCharArray();
		Arrays.sort(ca);
		dupPermute(ca, 0);
	}
	
	private static void dupPermute(char[] s, int position) {
		if (position == s.length - 1) {
			System.out.println(s);
		} else {
			char lastSwap = 0;
			for (int i = position; i < s.length; i++) {
				if (lastSwap == s[i]) {
					continue;
				} else {
					lastSwap = s[i];
				}
				
				swap(s, i, position);
				dupPermute(s, position + 1);
				swap(s, position, i);
			}
		}
			
	}
	
	private static void swap(char[] ca, int i, int j) {
		char tmp = ca[i];
		ca[i] = ca[j];
		ca[j] = tmp;
	}

	public static void main(String[] args) {
		String s = "aabc";
		Ch9_5.dupPermute(s);
	}
}
